package com.lw.leetcode.dp.b;

import java.util.TreeSet;

/**
 * Created with IntelliJ IDEA.
 * 1774. 最接近目标价格的甜点成本
 *
 * @author liw
 * @version 1.0
 * @date 2022/12/4 10:45
 */
public class ClosestCost {

    public static void main(String[] args) {
        ClosestCost test = new ClosestCost();

        // 10
//        int[] baseCosts = {1, 7};
//        int[] toppingCosts = {3, 4};
//        int target = 10;

        // 17
//        int[] baseCosts = {2, 3};
//        int[] toppingCosts = {4, 5, 100};
//        int target = 18;

        // 8
//        int[] baseCosts = {3, 10};
//        int[] toppingCosts = {2, 5};
//        int target = 9;

        // 10
//        int[] baseCosts = {10};
//        int[] toppingCosts = {1};
//        int target = 1;

        // 10
        int[] baseCosts = {23,56,89,4567,45,78,352,676,789,454};
        int[] toppingCosts = {86,57,38,388,665,790,457,567,873,888};
        int target = 450;

        int i = test.closestCost(baseCosts, toppingCosts, target);
        System.out.println(i);

    }

    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
        TreeSet<Integer> set = new TreeSet<>();
        int min = Integer.MAX_VALUE;
        int all = Integer.MAX_VALUE;
        for (int baseCost : baseCosts) {
            int v = target - baseCost;
            if (v == 0) {
                return target;
            }
            int t = Math.abs(target - baseCost);
            if (t < min || (t == min && baseCost < all)) {
                min = t;
                all = baseCost;
            }
            set.add(v);
        }
        int l = toppingCosts.length << 1;
        int[] arr = new int[l];
        int i = 0;
        for (int toppingCost : toppingCosts) {
            arr[i++] = toppingCost;
            arr[i++] = toppingCost;
        }
        int length = 1 << l;
        int[] items = new int[length];
        for (i = 1; i < length; i++) {
            int c = (i - 1) & i;
            int v = items[c] + arr[Integer.bitCount(i - c - 1)];
            items[i] = v;
            Integer t = set.floor(v);
            if (t != null) {
                int d = v - t;
                if (d < min || (d == min && target + d < all)) {
                    min = d;
                    all = target + d;
                }
            }
            t = set.ceiling(v);
            if (t != null) {
                int d = t - v;
                if (d < min || (d == min && target - d < all)) {
                    min = d;
                    all = target - d;
                }
            }
        }
        return all;
    }

}
